// 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 输入: `[-2,1,-3,4,-1,2,1,-5,4]`
// 输出: 6
// 解释: 连续子数组 `[4,-1,2,1]` 的和最大，为 6。
// 找到最大和的连续子数组
// 五部曲

// 1. dp数组的含义，`dp[i]`,i结尾的最大连续子数组和
// 2. 确定递推公式，`Math.max(nums[i] + dp[i-1], nums[i])`,其实就是这两种情况的最大值
// 3. 确定遍历顺序，从前往后
// 4. 初始值，`dp[0] = nums[0]`
// 5. 举例推导

// 最终返回的是dp中最大的值，而不是最后一个值

function maxSubArray(nums) {
    let dp = []
    dp[0] = nums[0]
    let result = nums[0]
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i]) 
        result = Math.max(result, dp[i])
    }
    return result
}

console.log(maxSubArray( [-2,1,-3,4,-1,2,1,-5,4]))